package liangtWorkSpace.suanfa;

// 归并排序
public class Merge2Sort {

    /**
     * 归并排序 -- 将两个数组按照大小顺序整合到新的数组
     * @param arrs
     */
    public static void sort(int[] arrs,int left,int right){
        System.out.println("******************************************");
//        merge(arrs,0,4,arrs.length - 1); // 排全部
        System.out.println(left + " ："+ right);
        //相等时停止
        if (left == right){
            return;
        }
        int min = left + (right -left)/2; // 防止int溢出 越界

        // 左半排序归并
        sort(arrs,left,min);
        // 右半排序并归
        sort(arrs,min+1,right);
        merge(arrs,left,min+1,right); // 排中间五个 3 4 6 7 8
        System.out.println("===========================================");
    }

    private static void merge(int[] arrs,int left , int right,int bound){
        System.out.println("left"+left);
        System.out.println("right"+right);
        System.out.println("bound"+bound);
        int min = right - 1;
        int[] temp = new int[bound - left + 1];

        int i = left;
        int j = right;
        int k = 0;

        // 将两个序列分别插入
        while (i <= min && j <= bound){
            temp[k++] = arrs[i] < arrs[j] ? arrs[i++]:arrs[j++];
            System.out.println("i = " + i + " j = " + j);
            SortUtils.print(temp);
            System.out.println();
        }

        //将没有循环完的数组复制到新数组末尾
        while (i <= min){ temp[k++] = arrs[i++]; }
        while (j <= bound){ temp[k++] = arrs[j++]; }
        SortUtils.print(temp);
        for (int l = 0; l < temp.length; l++) {
            arrs[left+l] = temp[l];
        }
    }


    public static void main(String[] args) {
//        int[] arrs = {1,4,7,8,3,6,9};
        int[] arrs = SortUtils.getArrays(15);
        sort(arrs,0,arrs.length-1);
    }

}
